package Lee_code;

import java.util.Arrays;

/**
 * @author blh
 * @date 2024年08月26日 15:41
 */
public class Lee_456_826 {
    public boolean find132pattern(int[] nums) {
        /*
        132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，
        并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
        如: 1 3 2
        */
        /**
         * 想办法实现 小 大 小 的排列顺序
         */
        int len = nums.length;
        int[] left = new int[len];
        int[] right = new int[len];
        // left 是左边的最小值left[i]是num[0] - num[i-1]的最小值
        left[0] = nums[0];
        for (int i = 1; i < len; i++) {
            left[i] = Math.min(nums[i], left[i - 1]);
        }
        right[len - 1] = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            right[i] = Math.min(nums[i], right[i + 1]);
        }
        for (int i = 1; i < len - 1; i++) {
            if (nums[i] > left[i - 1] && nums[i] < right[i + 1]) {
                return true;
            }
        }
        return false;
    }
}
